import { Node } from "./链表";
// 比较函数
function compare(a: CanCompare, b: CanCompare) {
  return a < b ? Compare.SMALLER : Compare.LARGGER;
}
// 排序列表类
class SortedLinkedList {
  protected length: number;
  protected dummy: Node<number>;
  protected head: Node<CanCompare> | null;
  protected next: Node<CanCompare> | null;
  // 构造函数
  constructor() {
    this.length = 0;
    this.dummy = new Node(0);
    this.head = null;
    this.dummy.next = this.head; // 哨兵节点插在头节点前
    this.next = null;
  }
  // 检查索引是否合理
  protected checkIndex(index: number): boolean {
    return index >= 0 && index <= this.length;
  }
  // 判断节点顺序
  protected getOrderIndex(val: CanCompare): number {
    let curr = this.head;
    let index = 0;
    while (curr != null) {
      const compareRes = compare(val, curr.val);
      if (compareRes === Compare.SMALLER) return index;
      curr = curr.next;
      index++;
    }
    return index;
  }
  // 根据索引插入节点
  protected insertByIndex(index: number, val: CanCompare): boolean {
    if (!this.checkIndex(index)) {
      console.warn("请检查插入的索引是否合理。");
      return false;
    } else {
      const curr = new Node(val);
      if (index === 0) {
        // 检查是否是在往头部插入
        curr.next = this.head;
        this.head = curr;
      } else {
        const previous = this.findNodeByIndex(index - 1); // 找前驱结点
        if (previous == null) throw console.trace(`意料之外的错误，输入参数${index},${val}`);
        curr.next = previous.next;
        previous.next = curr;
      }
      this.length++;
      return true;
    }
  }
  // 有序插入节点
  insert(val: CanCompare): boolean {
    if (this.isEmpty()) {
      this.insertByIndex(0, val);
      return true;
    } else {
      let index = this.getOrderIndex(val);
      const res = this.insertByIndex(index, val);
      return res;
    }
  }
  // 根据索引找节点
  findNodeByIndex(index: number): Node<CanCompare> | null {
    if (!this.checkIndex(index)) {
      return null;
    } else {
      let curr: Node<CanCompare> | null = this.head;
      for (let i = 0; i < index && curr; i++) {
        curr = curr.next;
      }
      return curr;
    }
  }
  // 根据索引删除节点
  deleteByIndex(index: number): Node<CanCompare> | null {
    if (!this.checkIndex(index)) {
      return null;
    } else {
      let curr: Node<CanCompare> | null = this.head;
      if (index === 0) {
        // 如果是要删除头节点
        this.head = this.head ? this.head.next : null;
      } else {
        const previous = this.findNodeByIndex(index - 1);
        if (previous == null) throw console.trace(`意料之外的错误，输入参数${index}`);
        curr = previous.next;
        previous.next = curr != null ? curr.next : null;
      }
      this.length--;
      return curr;
    }
  }
  // 根据值获取索引
  getIndexByVal(val: CanCompare): number {
    let curr: Node<CanCompare> | null = this.head;
    for (let i = 0; i < this.length && curr; i++) {
      if (curr.val === val) return i;
      curr = curr.next;
    }
    return -1;
  }
  // 获取链表长度
  getLength(): number {
    return this.length;
  }
  // 判断链表是否为空
  isEmpty(): boolean {
    return this.length === 0;
  }
  // 得到头节点
  getHead(): Node<CanCompare> | null {
    return this.head;
  }
  // 串行字符串化
  stringfy(): string {
    let str: string = "";
    let curr: Node<CanCompare> | null = this.head;
    for (let i = 0; i < this.length; i++) {
      str = str + curr?.val + "--->";
      curr = curr!.next;
    }
    return str.slice(0, -4); // 删除最后的箭头
  }
}

// 测试用例
const orderedList = new SortedLinkedList();
orderedList.insert(12);
orderedList.insert(11);
orderedList.insert(18);
orderedList.insert(1);
orderedList.deleteByIndex(3);
orderedList.deleteByIndex(10);
orderedList.deleteByIndex(4);
orderedList.deleteByIndex(0);
console.log(orderedList.getHead());
orderedList.insert(22);
orderedList.insert(0);
orderedList.deleteByIndex(1);
console.log(orderedList.findNodeByIndex(18));
console.log(orderedList.stringfy());
